Such techniques may be used in systems embedded in, for example, a semiconductor chip, or the like and examples of suitable applications of the storage apparatus include: smart cards such as Java Cards™; digital active storage or security devices such as smart keys and smart disks; SIMs (Subscriber IdentityModule) and USIMs (Universal Subscriber IdentityModule) for mobile telephones; data logging devices; small devices which record user preferences, store settings or record usage situations; computer systems in vehicles; set-top boxes; and internet routers.
The term “Persistent Data Item” or “PDI” as used herein is defined to be a data item having associated with it a variable value which changes over time, in particular when updated by an application program, and which is required to retain its state between such updates, particularly when the application is not running and when power is removed intentionally, when the application is switched off, or accidentally, for example because of a power failure.
Computer programs operate by reading and updating the values of variables. For variables in RAM, this presents little difficulty as the values can be rewritten as often as necessary and reading and writing of data are fast. When the program is not running, its recording state must be stored in more persistent memory.
On small computer platforms such as smart cards, there is little RAM and the persistent memory often takes the form of EEPROM or Flash memory. This persistent memory has the property that, once a bit has been changed, it is not changed again until the whole segment is erased. In EEPROM, the segment size may be as small as a single byte (8 bits) and the persistent memory can be treated essentially as very slow RAM. In flash memory, the segments have generally large (e.g. 64 KB) memory capacities for silicon area efficiency and the erase operation is also slow. Also, the life of the persistent memory will eventually ends after some number of erase cycles (say 100,000 for high quality Flash). The advantage of flash memory is that much more memories can be packed into a given chip area so there is more storage space, but it is harder than EEPROM, to use efficiently.
Consider a smart card application which keeps a record of the date and time (obtained from a card reader terminal, perhaps) on each occasion that it runs various processes and checks the interval between runs. This could be used for a security function, such as increasing an amount of a daily withdrawal limit for a cash card. Every time it runs various processes, it must read the old run date, check the interval and store the new run date. The run date is therefore a PDI (persistent data item). If the run date were stored in the same location each time it changes, the whole 64K block would first have to be erased because of the physical memory limitations and this would take a long time and rapidly wear out the flash memory and make its life short.
Instead, each time the new date is written, it must be stored in a new area of memory. It is assumed that this program has to share the flash memory with other programs, so it is not efficient to pre-allocate a large block of flash memory just for this one application. In other words, there may be many PDIs in the system and PDIs might be updated at different rates, depending on the applications running various processes.
A known arrangement as disclosed in “General-Purpose Persistence Using Flash Memory”, Jonathan T Moore, Michael Hicks, and Scott Nettles; Technical Report MS-CIS-97-3, CIS Dept. University of Pennsylvania, 1997, is to manage PDI (persistent data item) as (persistent data item) logs. Each time a PDI is updated, a log entry (update record) is written with the PDI's identity and the new value. To find the current value, the logs must be scanned to find the most recent value. When the block of the log entries (update record) is full, just the most recent values for each PDI can be copied to a fresh block, and the old block erased; this is called “garbage collection (collecting data recording areas which are not required any more for making them usable)”. This solution is efficient in flash memory space but, in view of the search times, reading values is slow. Some values can be cached (searched) by copying them to RAM, but this uses up valuable RAM space and also requires extra time to search the cache. Writing is fast because it just requires appending a log (update record).
Another known arrangement builds a linked chain of values for each PDI as illustrated in FIG. 8 of the accompanying drawings. The first element of the chain is at a known address. Each element of the chain stores a value for the run date record and has a space for a pointer to the next item in the chain. The last chain element will have a pointer value equal to the erased memory pattern (FFFF in hexadecimal in this model or 0000 in the complementary model). To read the current update date, reading starts at the beginning of the chain and sequentially follows pointers until one is reached with value FFFF. To add a new update date, a new chain element is created with the new value and an empty pointer. The address is then stored over the pointer part of the previous last-element. When garbage collecting, the last value in the chain is copied to the new block and used as the start of the new chain.    Example: chain representing the value “date2” (with previous values “date1” and “date0”).    Address Contents [value, pointer]
0120 [date0, 0236] // initial value = date0...0236 [date1, 0240] // value after first update = date1...0240 [date2, FFFF] // value after second update = date2    Now add the new value “date3”, and suppose there is free memory at address 0332:
0120 [date0, 0236]...0236 [date1, 0240]...0240 [date2, 0332]...0332 [date3, FFFF]
The program code to achieve this is simple and compact (here C style is used to explain the algorithm):
newtype element = record {value v, element* next}procedure updatevalue_chain(element* startaddress, valuenewvalue)  = {    element* p = startaddress;    element* newp = malloc(sizeof (element)); // spacefor new element       newp->v = newvalue; // store the new value inthe new element       while (p.next != 0xFFFF) // search for the endof the chain           do {p = p.next}       p.next = newp; // make the previous pointer pointto the new element       }
The problem is that, for each read or update, it is necessary to search through the whole chain of values. In a 64K memory segment, it might be necessary to search up to 16,000 entries (2+2 bytes per entry) when the chain is long and this is too slow in time to perform. If there are N entries, search time is proportional to N and the space required is (d+2) *N bytes, where d is the number of bytes to store a single value and pointers take two bytes. However, the solution is compact, each 2 byte value uses only 4 bytes for storage and, if the data stops being updated, at most 2 bytes at the end of the chain are wasted by being allocated but not used.
In another known arrangement as disclosed in “Data Management in a Flash Memory Based Storage Server”, Mei-ling Chiang, Paul C H Lee and Ruei-Chuan Chang; National Chiao-Tung University, Hsinchu, Taiwan, R.O.C. and Academia Sinica, Nankang, Taiwan, R.O.C., the flash memory is divided into sub-blocks which are managed by the system. Blocks have to be rewritten (i.e., new values written to a new area of flash memory and the old block marked in some way as out-of-date) as a whole. This means that, if the blocks are too large, then memory is wasted (e.g., using a block of 32 bytes to store a 2 byte counter). If the blocks are too small, then there are too many blocks and the management overhead is wasteful of CPU searching time or RAM space or both.
In yet another known arrangement as disclosed in “Architecture of the PEVM: a High-Performance Orthogonally Persistent Java™”, Brian Lewis, Bernd Mathiske, Neal Gafter; Sun-Microsystems, Inc., 901 San Antonio Road, Palo Alto, Calif. 94303-4900, USA, the contents of flash memory are managed as a virtual memory system with copy-on-write. Flash memory to be updated is copied into RAM and modified. If there is no space for the incoming block, then an old block is written back into flash. This can result in a whole block being rewritten because just a single byte in it has changed. This system adds a lot of time overhead to each access because lots of memory copying is required of blocks in and out of RAM.
In “Transacted Memory for Smart Cards”, Pieter H Hartel, Michael J Butler, Eduard de Jong and Mark Longley; fphh, mjbg@ecs.soton.ac.uk and Eduard.deJong@Sun.COM; Technical Report DSSE-TR-2000-9, Aug. 16, 2000; Declarative Systems and Software Engineering Group, Department of Electronics and Computer Science, University of Southampton, Highfield, Southampton SO17 1BJ, United Kingdom, a small block size is assumed (e.g., 32 bytes) in a smart card memory and we are shown how to build transactional objects. In these objects, updates to arbitrarily many data items are performed as one (atomically) and, if the transaction is aborted for any reason before completion, it returns to its original state.